class Solution
{
public:
    int minJumps(vector<int> &arr)
    {
        int n = arr.size();
        unordered_map<int, vector<int>> sameValIndex;
        for (int i = 0; i < n; ++i)
        {
            sameValIndex[arr[i]].push_back(i);
        }
        unordered_set<int> visited;
        queue<int> q;
        visited.insert(0);
        q.push(0);
        int step = 0;
        while (!q.empty())
        {
            int qSize = q.size();
            for (int _ = 0; _ < qSize; ++_)
            {
                int index = q.front();
                q.pop();

                if (index == n - 1)
                {
                    return step;
                }

                if (index > 0 && !visited.count(index - 1))
                {
                    q.push(index - 1);
                    visited.insert(index - 1);
                }
                if (index < n - 1 && !visited.count(index + 1))
                {
                    q.push(index + 1);
                    visited.insert(index + 1);
                }
                for (int i : sameValIndex[arr[index]])
                {
                    if (!visited.count(i))
                    {
                        q.push(i);
                        visited.insert(i);
                    }
                }
                sameValIndex[arr[index]].clear();
            }
            ++step;
        }
        return 0;
    }
};